package leetcode.code0264;

import java.util.TreeSet;

public class Solution64 {

	static int[] table = new int[1691];
	static {
		long ans = 0;
		TreeSet<Long> min = new TreeSet<>((a, b) -> (int) (a - b));
		min.add(1l);
		int n = 1690;
		int i = 1;
		while (n > 0) {
			ans = min.first();
			min.remove(ans);
			if (ans * 2 <= Integer.MAX_VALUE)
				min.add(ans * 2);
			if (ans * 3 <= Integer.MAX_VALUE)
				min.add(ans * 3);
			if (ans * 5 <= Integer.MAX_VALUE)
				min.add(ans * 5);
			table[i++] = (int)ans;
			n--;
		}
	}

	public int nthUglyNumber(int n) {
		return table[n];
	}

	public static void main(String[] args) {
		Solution64 so = new Solution64();

//		for(int i=1;i<11;i++) {
//			System.out.println(so.nthUglyNumber(i));
//		}
		System.out.println(so.nthUglyNumber(1447));
	}

}
